package backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

public class LeetCode39 {
    /**
     * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     * 说明：
     * 所有数字（包括目标数）都是正整数。
     * 解集不能包含重复的组合。
     * 示例 1:
     **/
    List<List<Integer>> result = new ArrayList<>();
    int[] candidates;
    int target;
    int value;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.target = target;
        Arrays.sort(candidates);
        this.candidates = candidates;
        ArrayList<Integer> list = new ArrayList<>();
        backtrack(list);
        return result;
    }
    public void backtrack(List<Integer> list){
        if(value == target){
            result.add(new ArrayList<>(list));
            Integer integer = list.get(list.size() - 1);
            value -= integer;
            list.remove(list.size() - 1);
            return;
        }
        for (int candidate : this.candidates) {
            value += candidate;
            list.add(candidate);
            if(value > target) {
                Integer integer = list.get(list.size() - 1);
                value -= integer;
                list.remove(list.size() - 1);
                break;
            };
            backtrack(list);
        }
        if(list.size() > 0){
            Integer integer = list.get(list.size() - 1);
            value -= integer;
            list.remove(list.size() - 1);
        }
    }
    public List<List<Integer>> combinationSum1(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 先进行排序
        backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }

    public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
        // 找到了数字和为 target 的组合
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            // 如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backtracking(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
        }
    }
    public static void main(String[] args) {
        LeetCode39 leetCode39 = new LeetCode39();
//        leetCode39.combinationSum(new int[]{2,3,6,7}, 7);
//        System.out.println(leetCode39.result);
        List<List<Integer>> lists = leetCode39.combinationSum1(new int[]{2, 3, 6,7}, 7);
        System.out.println(lists);
    }
}
